Although the idea of inserting a chip into a plastic card is relatively old (first patents are now seventeen years old), practical applications only emerged a few years ago because of some computational limitations of the chips. Progress in storage capacity, security and circuit technology (for example EEPROM) led quickly to new generations of cards and more ambitious applications such as the new emerging US Digital Signature Standard, which itself renders significant many new kinds of transactions.
This DSA was proposed by the US National Institute of Standards and Technology (NIST) to provide an appropriate core for applications requiring a digital. rather than written signature. The DSA digital signature is a pair "r and s" of large numbers represented in a computer as strings of binary digits. The digital signature is computed using a set of rules (i.e. the DSA) and a set of parameters such that the identity of the signatory and integrity of the data can be verified. The DSA provides the capability to generate and verify signatures.
Signature generation makes use of a private key "x" to generate a digital signature. Signature verification makes use of a public key "y" which corresponds to, but is not the same as, the private key. Each user possesses a private and a public key pair. Public keys are assumed to be known to the public in general whereas private keys are never shared. Anyone can verify the signature of a user by employing that user's public key. Signature generation can be performed only by the user's private key.
DSA parameters are:
1--a first module p where 2.sup.L&lt;1 &lt;p&lt;2.sup.L for 512.ltoreq.L.ltoreq.1024 and L=64.alpha. for some .alpha.. Practically p is a string of L bits, for example 512 bits.
2--a second module q such that 2.sup.159 &lt;q&lt;2.sup.160 and p-1 is a multiple of q. Practically q is a string of 160 bits. Meanwhile it could be different.
3--a number g, of order q modulo p such that g=h.sup.(p-1) /q modulo p, where h is any integer such that 1&lt;h&lt;p-1 and where g is greater than 1.
4--a number x, defined randomly or pseudo randomly and which is the private key.
5--a number y, defined by the relation y=g.sup.x modulo p, which is the public key.
6--a number k generated randomly or pseudo randomly such that 0&lt;k&lt;q.
The integers p, q and g are system parameters and can be public and/or common to a group of users. The user's private and public keys are respectively x and y. Parameters x and k are used for signature generation only and must be kept secret. Parameter k must be regenerated for each signature. Parameter y is shared by many groups of users.
In order to sign a message m (hashed value of a primitive binary file M), a signer computes the signature "r and s". A hashed value m of a primitive file M is a binary rearranged string of some (or all) of the bits of M. A signer is practically a microprocessor of the chip card of the user which performs a programmed operation. This operation may be performed automatically at the end of the edition of the primitive file M or the message m. It may also be performed at a will after this edition. The computation made for this signature which is particularly depicted in KNUTH, is as follows: r=(g.sup.k modulo p) modulo q and s=((m+xr)/(k))modulo q. The first part r of the signature is dependant on the used system by g p q and k, while s is dependant on the message m and the private key x, and also q r k.
In this signature a division by k is done modulo q (that is 1/k is the number k' such that kk'.tbd.1 modulo q). For instance, if q=5 and k=3 then 1/k modulo 5=2, as a matter of fact 1/3=2 modulo 5 since 3.times.2=6.tbd.1 modulo 5.
After checking that r is different from 0 and from s, as explained in the DSA description, the signature "r and s" is ready. This signature authenticates that the message m was provided by the owner of the chip card with his correct private key "x". It is then sent together with the message m to a verifier authority.
This verifier authority makes a verification of what is received with a verifier. A verifier, which practically comprises a processor performing a verification program, makes a batch verification. When this batch verification is made the message m is authenticated, it is recognised that this message issued from an authorised user, and the economical consequences of this message may be then validated. That means that the verifier authority may perform an action related to the message m, that means for example authorising a transaction between the user of the chip card and a trader and performing corresponding funds transfers or even authorising a transaction between this user and the verifier authority.
DSS batch verification allows a verifier to delay the verification of a set of DSS signatures until he decides that he has an enough big quantity of these and then verify all of them at once.
Such an approach is advantageous in many practical a situations. for example banks send and receive transaction orders during all the day but execute (inter-compensate) them during the night. Pay-TV subscribers purchase viewing rights from a program provider that has to check the individual validity of each purchasing order before downloading the rights over-the-air. Similar situations are frequently met in many other electronic transactions.
More generally, batch signature verification is useful whenever a certain time, that allows a reverse operation, a censorship or an opposition action, separates the signature from its consequence (typically the delivery of the goods or services to the user-signer).
The verifier computes:
1--w=1/s modulo q (since it knows the publicly shared value q ant it receives s). Should it exist many groups of users with different sets of p q g numbers, they are sent to the verifier at a same time as the message m and the r and s signature.
2--u.sub.1 =m w modulo q (since it knows m received, q shared and w previously computed).
3--u.sub.2 =r w modulo q (since it knows r received, q shared and w previously computed).
4--v=(g.sup.u 1.multidot.y.sup.u 2 modulo p) modulo q (since u.sub.1 and u.sub.2 are previously computed and y is the public key for the group of users).
Then it checks if v and r match to accept or reject the signature. That is too long when too many verifications have to be made